package woa.tree.binary;

/**
 * 从中序与后序遍历序列构造二叉树
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 * 注意:
 * 你可以假设树中没有重复的元素。
 * 例如，给出
 * 中序遍历 inorder = [9,3,15,20,7]
 * 后序遍历 postorder = [9,15,7,20,3]
 *
 * 返回如下的二叉树：
 *     3
 *    / \
 *   9  20
 *  /    \
 * 15     7
 *
 * @author wangpeng
 * @date 2021/12/4
 */
public class BuildTree1 {

    static int[] inorderArr;
    static int[] postorderArr;
    static int p;


    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        p = postorder.length - 1;
        inorderArr = inorder;
        postorderArr = postorder;
        return dfs(0, p);
    }

    public static TreeNode dfs(int m, int n) {
        if (m > n) {
            return null;
        }
        int i = n;
        while (i >= m) {
            if (inorderArr[i] == postorderArr[p]) {
                break;
            }
            --i;
        }
        --p;
        TreeNode root = new TreeNode(inorderArr[i]);
        root.right = dfs(i + 1, n);
        root.left = dfs(m, i - 1);

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = buildTree(new int[]{4,9,6,3,15,20,7}, new int[]{4,6,9,15,7,20,3});
        System.out.println(root);
    }
}
